#ifndef _core_dispatch_type_lookup_binary_search_hpp_
#define _core_dispatch_type_lookup_binary_search_hpp_

/** \file binary_search.hpp
 *  \author Adrian Schweizer
 *  \created  $Sa 18 Aug 03:48:01 pm CEST 2007 schwadri@SchwadriComp.local$
 *  \modified $So 19 Aug 03:48:03 pm CEST 2007 schwadri@SchwadriComp.local$
 */


#include <boost/type_traits/function_traits.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/begin.hpp>
#include <boost/mpl/end.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/erase.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/integral_c.hpp>
#include <boost/mpl/advance.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/is_sequence.hpp>
#include <boost/mpl/assert.hpp>

#include "detail/default.hpp"

namespace core {

    namespace dispatch {

        namespace type_lookup {

            //binary search implementation for mpl::vector
            namespace vector {

                template<int TypesSize,
                         int Offset,
                         class Types,
                         class ReturnValue>
                    struct FindActionType
                    {
                        template<class Key, class Invoker, class Default>
                        static ReturnValue eval(Key key, Invoker& i, Default d)
                        {
                            if(key > Offset+(TypesSize/2))
                            {
                                typedef typename boost::mpl::begin<Types>::type first;
                                typedef boost::mpl::int_< (TypesSize/2)+1 > new_ofs;
                                typedef typename boost::mpl::advance<first,new_ofs >::type last;
                                typedef typename boost::mpl::erase<Types,first,last>::type upper_range;
                                typedef FindActionType<boost::mpl::size<upper_range>::type::value,
                                                        (new_ofs::value+Offset),
                                                        upper_range,
                                                        ReturnValue>                upper_range_search;

                                return upper_range_search::template eval<Key,Invoker,Default>(key,i,d);
                            }
                            else if(key < Offset+(TypesSize/2))
                            {
                                typedef typename boost::mpl::begin<Types>::type begin;
                                typedef boost::mpl::int_< (TypesSize/2) > new_ofs;
                                typedef typename boost::mpl::advance<begin,new_ofs >::type first;
                                typedef typename boost::mpl::end<Types>::type last;
                                typedef typename boost::mpl::erase<Types,first,last>::type lower_range;
                                typedef FindActionType<boost::mpl::size<lower_range>::type::value,
                                                        Offset,
                                                        lower_range,
                                                        ReturnValue>                lower_range_search;

                                return lower_range_search::template eval<Key,Invoker,Default>(key,i,d);
                            }
                            else
                                return i.template invoke<typename boost::mpl::at<Types,boost::mpl::int_< (TypesSize/2) > >::type>();
                        }
                    };

                template<int O, class T, class R>
                    struct FindActionType<1,O,T,R>
                    {
                        template<class K, class I, class D>
                            static R eval(K k, I& i, D d)
                            {
                                if(k==O)
                                    return i.template invoke<typename boost::mpl::front<T>::type>();
                                else
                                    return d(k);
                            }
                    };

                template<int O, class T, class R>
                    struct FindActionType<0,O,T,R>
                    {
                        template<class K, class I, class D>
                            static R eval(K k, I& i, D d)
                            {
                                return d(k);
                            }
                    };

                struct get_bin_search_impl
                {
                    template<int CasesSize, class Cases, class ReturnValue>
                        struct apply
                        {
                            typedef FindActionType<CasesSize,0,Cases,ReturnValue> type;
                        };
                };

            } // namespace vector

            namespace detail {

                template<class SequenceTag>
                    struct get_bin_search_impl;
                    /*{

                        //and that it is a vector (everything else is not supported)
                        //BOOST_MPL_ASSERT((boost::type_traits::is_same<SequenceTag,boost::mpl::aux::map_tag>));
                    };*/

                template<>
                    struct get_bin_search_impl<boost::mpl::aux::vector_tag>
                    {
                        typedef vector::get_bin_search_impl type;
                    };

            } // namespace detail

            /** \brief key value to type mapping using binary search
             *
             *  this implementation builds a cascade of if else blocks performing
             *  a binary search
             *  \note only a boost::mpl::vector is allowed for the type list
             */
            template<class Types>
                class binary_search
                {
                public:

                    typedef binary_search<Types> type;

                    template<class Key, class Invoker>
                        typename Invoker::return_type type_lookup(Key key, Invoker& invoker)
                        {
                            //first check that Types is in fact a sequence
                            BOOST_MPL_ASSERT((boost::mpl::is_sequence<Types>));
                            typedef typename boost::mpl::sequence_tag<Types>::type              sequence_tag;
                            typedef typename detail::get_bin_search_impl<sequence_tag>::type    impl_type;
                            typedef typename Invoker::return_type                               return_type;


                            typedef typename impl_type::template apply<boost::mpl::size<Types>::value,
                                                                        Types,
                                                                        return_type
                                                                        >::type         search_impl;

                            return search_impl::template eval<Key,Invoker,
                                    detail::throw_unhandled_key<return_type,Key> >(key,invoker,
                                                                                    detail::throw_unhandled_key<return_type,Key>());
                        }

                };
        } // namespace type_lookup
    } // namespace dispatch
} // namespace core

#endif // _core_dispatch_type_lookup_binary_search_hpp_
